import java.util.*;


public class Solution12 {
    public static void main(String[] args) {
        Solution12 solution =new Solution12();
        List<String> list= new ArrayList<>();
        list.add("hot");
        list.add("dot");
        list.add("dog");
        list.add("lot");
        list.add("log");
        list.add("cog");
        int i = solution.ladderLength("hit", "cog", list);
        System.out.println(i);
    }
    String enums = "abcdefghijklmnopqrstuvwxyz";
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<String>(wordList);
        //采用广度优先搜索
        if(!wordSet.contains(endWord))return 0;
        char[] chars = enums.toCharArray();
        Deque<String> deque = new LinkedList<String>();
        deque.add(beginWord);
        int nums = 0;
        while(!deque.isEmpty()){
            nums++;
            for(int count = deque.size();count>0;count--){
                char[] pollChars = deque.poll().toCharArray();
                for(int i =0;i<pollChars.length;i++){
                    char oldChar = pollChars[i];
                    for(int j=0;j<chars.length;j++){
                        pollChars[i] = chars[j];
                        String temp = new String(pollChars);
                        if(endWord.equals(temp)){
                            System.out.println(temp);
                            return nums;
                        }
                        if(wordSet.contains(temp)){
                            System.out.println(temp);
                            deque.add(temp);
                            wordSet.remove(temp);
                        }
                    }
                    pollChars[i]=oldChar;
                }
            }
        }
        return 0;
    }
}
